package threshold;

import java.util.Scanner;

/**
 * @Author wujiaming
 * @Description TODO
 * @Date 2023-03-14 17:33
 * @Version 1.0
 */
public class JinZhiZhuanHua {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        while(sc.hasNextInt()){
            for (int i = 0; i <N ; i++) {
                int num = sc.nextInt();
                int jinZhi = sc.nextInt();
                String s = Integer.toString(num, jinZhi);
                System.out.println(s.toUpperCase());
            }

        }

    }
}
